class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool vis[15][15] = {false};
    int dist[15][15] = {0};
    int cnt[15][15] = {0};
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        memset(dist, -1, sizeof dist);
        memset(cnt, 0, sizeof cnt);
        memset(vis, false, sizeof vis);
        int x = 0, y = 0;
        int rx = 0, ry = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1) {
                    x = i, y = j;
                }
                if (CityMap[i][j] == 2) {
                    rx = i;
                    ry = j;
                }
            }
        }
        bfs(CityMap, x, y, n, m);
        return cnt[rx][ry];
    }
    void bfs(vector<vector<int> >& CityMap, int x, int y, int& mx, int& my) {
        queue<pair<int, int>> q;
        q.push({x, y});
        vis[x][y] = true;
        dist[x][y] = 0;
        cnt[x][y] = 1;
        while (q.size()) {
            auto node = q.front();
            q.pop();
            int tx = node.first;
            int ty = node.second;
            for (int i = 0; i < 4; i++) {
                int x1 = tx + dx[i];
                int y1 = ty + dy[i];
                if (x1 >= 0 && x1 < mx && y1 >= 0 && y1 < my  && !vis[x1][y1] &&
                        CityMap[x1][y1] != -1) {
                    vis[x1][y1] = true;
                    dist[x1][y1] = dist[tx][ty] + 1;
                    cnt[x1][y1] = cnt[tx][ty];
                    if (CityMap[x1][y1] != 2) q.push({x1, y1});
                } else if (x1 >= 0 && x1 < mx && y1 >= 0 && y1 < my && CityMap[x1][y1] != -1 &&
                           dist[x1][y1] == (dist[tx][ty] + 1)) {
                    cnt[x1][y1] += cnt[tx][ty];
                }
            }
        }
    }
};